/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package lab2mergesort;

import java.util.Random;
/**
 *
 * @author Daryna_Ragimova
 */


public class Sort {

    private static final int numberOfThreads = 4;//Runtime.getRuntime().availableProcessors();
    private static final int n = 100;
    private static Integer[] items = new Integer[n];

    

    public static Integer[] sort(Integer[] data, int numberOfThreads) {
        return mergesort(data, 0, data.length - 1, numberOfThreads);
    }

    private static Integer[] mergesort(Integer[] data, int firstIndex, int lastIndex, int numberOfThreads) {
        if (firstIndex > lastIndex) {
            return new Integer[0];
        } else if (firstIndex == lastIndex) {
            return new Integer[]{data[firstIndex]};
        }
        int midIndex = (firstIndex + lastIndex) / 2;

        Integer[] left = null;
        Thread otherThread = null;
        MergeThread other = null;

        if (numberOfThreads > 1) {
            // spawn
            other = new MergeThread(data, firstIndex, midIndex, numberOfThreads / 2);
            otherThread = new Thread(other);
            otherThread.start();
        } else {
            left = mergesort(data, firstIndex, midIndex, numberOfThreads / 2);
        }
        Integer[] right = mergesort(data, midIndex + 1, lastIndex, 
                numberOfThreads - (numberOfThreads / 2));

        if (numberOfThreads > 1) {
            try {
                // sync
                otherThread.join();
            } catch (InterruptedException e) {
            }
            left = other.getResult();
        }
        
        return merge(left, right);
    }

    private static Integer[] merge(Integer[] a1, Integer[] a2) {
        Integer[] result = new Integer[a1.length + a2.length];

        int i1 = 0;
        int i2 = 0;

        for (int j = 0; j < result.length; ++j) {
            if (i2 >= a2.length) {
                result[j] = a1[i1++];
            } else if (i1 >= a1.length) {
                result[j] = a2[i2++];
            } else if (a1[i1].compareTo(a2[i2]) <= 0) {
                result[j] = a1[i1++];
            } else {
                result[j] = a2[i2++];
            }
        }
        return result;
    }

    private static void showArray(Integer[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    private static class MergeThread implements Runnable {

        int firstIndex;
        int lastIndex;
        int numberOfThreads;
        
        Integer[] result;
        Integer[] data;

        public MergeThread(Integer[] data, int firstIndex, int lastIndex, int numberOfThreads) {
            this.data = data;
            this.firstIndex = firstIndex;
            this.lastIndex = lastIndex;
            this.numberOfThreads = numberOfThreads;
        }

        @Override
        public void run() {
            result = mergesort(data, firstIndex, lastIndex, numberOfThreads);
        }

        public Integer[] getResult() {
            return result;
        }
    }
    public static void main(String[] args) {

        Random r = new Random();
        for (int i = 0; i < items.length; ++i) {
            items[i] = new Integer(r.nextInt(1000));
        }

        showArray(items);

        //long start = System.currentTimeMillis();
        items = sort(items, numberOfThreads);
        showArray(items);
        //long end = System.currentTimeMillis();

        //System.out.println("Time: " + (end - start) + " ms");
    }
}
